package likou.offer2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/11/02 08:26
 */
public class _015 {
    public static void main(String[] args) {
        _015 o = new _015();
        System.out.println(o.findAnagrams("cbaebabacd",
                "abc"));
    }
    public List<Integer> findAnagrams(String s2, String s1) {
        List<Integer> list = new ArrayList<>();
        int m = s1.length(), n = s2.length();
        int[] target = new int[26];
        char[] a1 = s1.toCharArray(),a2 = s2.toCharArray();
        for(int i = 0;i<m;i++){
            target[a1[i] - 'a'] --;
        }
        int left = 0;
        for(int right = 0;right < n;right++){
            int r = a2[right] - 'a';
            target[r] ++ ;
            while(target[r] > 0){
                target[ a2[left++] - 'a' ] --;
            }
            if(right - left +1 == m){
                list.add(left);
                target[a2[left]-'a']--;
                left++;
            }
        }
        return list;
    }
}
